#include <stdlib.h>
#include <stdio.h>
#include "malloc.h"

#define align4(x) (((((x) - 1) >> 2) << 2) + 4)

void *base = NULL;  // start of heap

t_block find_block(t_block *last, size_t size) {
    t_block b = base;
    while (b && !(b->free && b->size >= size))
    {
        *last = b;
        b = b->next;
    }
    
    return b;
}

t_block extend_heap(t_block last, size_t s) {
    t_block b;

    b = sbrk(0);

    // printf("BLOCK_SIZE + s: %lu\n", BLOCK_SIZE + s);
    if (sbrk(BLOCK_SIZE + s) == (void *)-1) {
        return NULL;
    }

    b->size = s;
    b->next = NULL; b->prev = NULL;
    if (last) {
        last->next = b;
        b->prev = last;
    }
    b->free = 0;
    return b;
}

t_block split_block(t_block b, size_t s) {
    t_block new;

    // new's position: [b + BLOCK_SIZE + b->size]; new's size: [b->size - s - BLOCK_SIZE]
    new = (t_block) b->data + s;
    // new = b->data + s;
    new->size = b->size - s - BLOCK_SIZE;
    new->next = b->next; new->prev = b;
    new->free = 1;

    // b's size: [s], b's next: [new]
    b->size = s;
    b->next = new;
    return b;
}

void *ff_malloc(size_t size) {
    t_block b, last;
    size_t s;
    s = align4(size);

    if (base) {
        // first find a block
        last = base;
        b = find_block(&last, s);

        if (b) {
            // enough space to split
            if ( (b->size - s) >= (BLOCK_SIZE + 4) )
                b = split_block(b, s);
            b->free = 0;
        }
        else {
            // no fitting block, extent the heap
            b = extend_heap(last, s);
            if (!b) return NULL;
        }
    } else {
        // first allocation
        b = extend_heap(NULL, s);

        if (!b) return NULL;
        base = b;
    }

    return b->data;
}

void *ff_calloc(size_t number, size_t size) {
    size_t *new;
    new = ff_malloc(number * size);
    if (new) {
        size_t s4 = align4(number * size) << 2;  // 8*4 bits as a unit
        for (size_t i = 0; i < s4; i++) {
            new[i] = 0;
        }
    }
    return (new);
}

t_block fusion(t_block b) {
    if (b->next && b->next->free) {
        // merge
        b->size += b->next->size + BLOCK_SIZE;
        b->next = b->next->next;
        if (b->next) {
            b->next->prev = b;
        }
    }
    return b;
}

t_block get_block(void *p) {
    char *tmp;
    p = tmp - BLOCK_SIZE;
    return p;
}

int valid_addr(void *p) {
    if (p) {
        if (p > base && p < sbrk(9)) {
            // t_block->ptr is used to verify whether p is in the heap
            return ( p == (get_block(p)->ptr) );
        }
    }
    return 0;
}

void ff_free(void *p) {
    t_block b;
    if (valid_addr(p)) {
        b = get_block(p);
        b->free = 1;
        // fuse with previous block
        if (b->prev && b->prev->free) {
            fusion(b->prev);
        }
        // fuse with next block
        if (b->next) {
            fusion(b);
        } else {
            // b is the endding block
            if (b->prev) b->prev->next = NULL;
            else base = NULL;
            brk(b);  // return extra mem to sys
        }
    }
    // else silently do nothing
}

void copy_block(t_block src, t_block dst) {
    int *sdata, *ddata;
    sdata = (int *)src->data; ddata = (int *)dst->data;
    for(size_t i = 0; i*4 < src->size && i*4 < dst->size; i++) {
        dst[i] = src[i];
    }
}
